#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

void Init(Tree *tree, datatype ref)
{
     tree->root = NULL;
     tree->refvalue = ref;
}

void Create(Tree *tree, char *str)
{
     Create_(tree, &tree->root, &str);
}

void Create_(Tree *tree, TreeNode **node, char **str) //以这棵树等价的二叉树来创建
{
     if (**str == tree->refvalue)
          *node = NULL;
     else
     {
          TreeNode *current = malloc(sizeof(TreeNode));
          if (current == NULL)
               return;
          current->data = **str;
          *node = current;
          (*str)++;
          Create_(tree, &current->firstChild, str);
          (*str)++;
          Create_(tree, &current->nextSibling, str);
     }
}

TreeNode *Root(Tree *tree)
{
     return tree->root;
}

TreeNode *firstChild(TreeNode *node)
{
     if (node == NULL)
          return NULL; //树为空
     return node->firstChild;
}

TreeNode *nextSibling(TreeNode *node)
{
     if (node == NULL)
          return NULL; //树为空
     return node->nextSibling;
}

TreeNode *Find(Tree *tree, datatype key)
{
     return Find_(tree->root, key);
}

TreeNode *Find_(TreeNode *node, datatype key)
{
     if (node == NULL)
          return NULL;
     if (node->data == key)
          return node;
     TreeNode *p = Find_(node->firstChild, key);
     if (p != NULL)
          return p;
     return Find_(node->nextSibling, key);
}

TreeNode *Parent(Tree *tree, TreeNode *node)
{
     return Parent_(tree->root, node);
}

TreeNode *Parent_(TreeNode *root, TreeNode *node)
{
     if (root == NULL || node == NULL || root == node)
          return NULL;
     TreeNode *current = root->firstChild, *parent;

     while (current != NULL && current != node)
     {
          parent = Parent_(current, node); //以该结点为根递归查找

          if (parent != NULL)
               return parent;
          else
               current = current->nextSibling; // parent为空,进入右兄弟结点查找
     }
     if (current != NULL && current == node)
          return root; //找到返回父结点
     return NULL;      //没找到
}

void PreOrder(TreeNode *root)
{
     if (root == NULL)
          return;
     printf("%c ", root->data);
     PreOrder(root->firstChild);
     PreOrder(root->nextSibling);
}